\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}

\title{作业三: 将AVLTree的数据从小到大输出}


\author{夏知人 \\ 信息与计算科学  3210103669}

\begin{document}

\maketitle



\section{设计思路}
主要是通过递归实现。先判断当前节点的key值是否位于给定的k1和k2之间。若当前节点的值是否位于给定的k1和k2之间，
则先递归当前节点的左儿子节点，不断重复此过程。当左儿子节点的递归结束后，输出当前节点的key值。再递归当前节点
的右儿子节点，不断重复此过程。若当前节点的值比给定的k1小，则递归当前节点的右儿子节点；若当前节点的值比给定的
k2大，则递归当前节点的左儿子节点。通过分析可以发现，当递归不断进行下去时，总是先输出比当前节点的key值较小的
节点的key值，然后再输出当前节点的key值，而比当前节点的key值大的节点总是后输出于当前节点。这样就能实现先输出
对应key值较小的节点，再输出对应key值较大的节点。而遇到当前节点是空指针则返回；遇到当前节点的值比给定的k1小，
则递归当前节点的右儿子节点；遇到当前节点的值比给定的k2大，则递归当前节点的左儿子节点；则保证了在递归过程中所
输出的key值与递归的范围总在给定的k1和k2之间。通过在输出时设置计数器，可以在递归结束时输出递归次数、访问节点
个数与所打印的键的个数。

\section{理论分析}
访问的结点是符合答案中的结点，或是为了找到符合答案的结点而访问的结点。通过程序设置计数器，将访问的节点数记为K个。
分析可得，若在一次查询中找到要寻找的节点，最多的查询次数等于树的高度，也就是log（n）个。每一层最多有两个该类型的
节点，查询要寻找的节点即为该子树的高度加上该节点到AVL树根节点的深度，所以查询要寻找的节点所访问的节点个数，最多
不超过2log(n)+K个。综上所述，时间复杂度为O(K+log(n))。
\section{数值结果分析}
通过不断改变N的值，测试寻找访问节点个数K与时间复杂度的关系
\begin{verbatim}
N=5000              K=2500           K+log(N)=2508.52     访问节点个数：2505
N=7000              K=4500           K+log(N)=4508.85     访问节点个数：4505
N=10000            K=5001           K+log(N)=5010.21     访问节点个数：5012
N=50000            K=5001           K+log(N)=5011.82     访问节点个数：5014
N=100000          K=5001           K+log(N)=5012.51     访问节点个数：5015
N=114514          K=5001           K+log(N)=5012.65     访问节点个数：5015


\end{verbatim}
经测试，访问节点个数K的值接近K+log（n），从而得出结论，时间复杂度为O(K+log(n))。
\end{document}
